class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = -1


class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        tree = Node('#')
        out = []
        for k, word in enumerate(words):
            node = tree
            for i in range(len(word)):
                if word[i] not in node.neighbors:
                    new_node = Node(word[i])
                    node.neighbors[word[i]] = new_node
                    node = new_node
                else:
                    node = node.neighbors[word[i]]
            node.flag = k

        def search(node, m, k):
            if node.flag >= 0:
                new_word = words[node.flag][m:]
                if new_word == new_word[::-1]:
                    out.append([node.flag, k])
            for next_node in node.neighbors:
                search(node.neighbors[next_node], m, k)

        for k, word in enumerate(words):
            m = len(word)
            node = tree
            i = 0
            while i < m:
                if node.flag >= 0:
                    new_word = word[: m - i]
                    if new_word == new_word[::-1]:
                        out.append([node.flag, k])
                if word[m - 1 - i] in node.neighbors:
                    node = node.neighbors[word[m - 1 - i]]
                    i += 1
                else:
                    break
            if i == m:
                if node.flag >= 0 and k != node.flag:
                    out.append([node.flag, k])
                for next_node in node.neighbors:
                    search(node.neighbors[next_node], m, k)
        return out


data = Solution()
words = ["abcd", "dcba", "lls", "s", "sssll"]
print(data.palindromePairs(words))
words = ["ab", "ba"]
print(data.palindromePairs(words))
words = ["a", ""]
print(data.palindromePairs(words))
